Собственно речь пойдет о двоичной куче и ее построении с помощью Sift-Down(или Heapify). Многим наверное известно, что построение кучи таким образом осуществляется за . Здесь я приведу доказательство этого факта. Вот пример процедуры построения кучи по массиву на языке Pascal. … Читать далее Двоичная куча: доказательство сложности построения О(n)